﻿// <copyright file="ConnexityProvider.cs" company="Ecole Normale Supérieure">
// Released under GPLv2
// </copyright>
// <summary>Contains the class ConnexityProvider</summary>

namespace Sqwarea.GameLogic.Connexity
{
    using System;
    using System.Collections.Generic;
    using System.Drawing;
    using System.Linq;
    using Extensions;
    using Persistence;

    /// <summary>
    /// Class for verifying whether an attack breaks connexity, and to repair connexity in that case.
    /// Also used to maintain the invariant of connexity through attacks.
    /// </summary>
    public class ConnexityProvider : IConnexityProvider
    {
        /// <summary>
        /// Initializes a new instance of the ConnexityProvider class
        /// </summary>
        /// <param name="gameProvider">The interface to use to get access to the game elements</param>
        /// <param name="queueProvider">The interface to use in case ConnexityAnnexSquare needs to call EnforceConnexity.</param>
        /// <param name="logProvider">The interface to make logs in case of loss of connexity..</param>
        public ConnexityProvider(IGameProvider gameProvider, IQueueProvider queueProvider, ILogProvider logProvider)
        {
            if (null == gameProvider)
            {
                throw new ArgumentNullException("gameProvider", "ConnexityProvider");
            }

            if (null == gameProvider)
            {
                throw new ArgumentNullException("queueProvider", "ConnexityProvider");
            }

            if (null == logProvider)
            {
                throw new ArgumentNullException("logProvider", "ConnexityProvider");
            }

            LogProvider = logProvider;
            GameProvider = gameProvider;
            QueueProvider = queueProvider;
        }

        /// <summary>
        /// Gets the GameProvider used by the buffer
        /// </summary>
        public IGameProvider GameProvider { get; private set; }

        /// <summary>
        /// Gets the LogProvider used by the buffer
        /// </summary>
        public ILogProvider LogProvider { get; private set; }

        /// <summary>
        /// Gets the QueueProvider used by ConnexityAnnexSquare in case of an anomaly.
        /// </summary>
        public IQueueProvider QueueProvider { get; private set; }

        /// <summary>
        /// Verify if connexity is broken, and if it is, it repairs it any way it can, even partially.
        /// Needs not only the square, but also its former owner,
        /// Because, ownership have already changed due to an attack
        /// Called by AttackSolver.
        /// </summary>
        /// <param name="breakpoint">Wrapper upon the coordinates of the case to be examined and the Id of its former King</param>
        /// <returns>True iff it has succeeded to repair connexity fully</returns>
        public bool EnforceConnexity(ConnexityBreakpoint breakpoint)
        {
            var buffer = new ConnexityBuffer(GameProvider);
            var baseSquare = buffer.GetSquareByPosition(breakpoint.Position);
            var formerKing = GameProvider.GetKingById(breakpoint.FormerKingId);

            var inProcessing = new HashSet<Square>();
            var todo = new Stack<Square>();

            var connexityWasNotLost = true;

            foreach (var baseNeighbour in buffer.GetNeighbours(baseSquare))
            {
                // In case several parts are deconnexified, each square adjacent to the baseSquare is treated separetely.
                if (
                    baseNeighbour.KingId != formerKing.Id ||
                    ! baseNeighbour.PointsTo(baseSquare) ||
                    baseNeighbour.HasKing)
                {
                    // We consider only potential connexity breaks
                    continue;
                }

                todo.Push(baseNeighbour);
                inProcessing.Add(baseNeighbour);
                while (todo.Count != 0)
                {
                    var poppedSquare = todo.Pop();
                    foreach (var neighbour in buffer.GetNeighbours(poppedSquare))
                    {
                        if (
                            neighbour.KingId != formerKing.Id || 
                            inProcessing.Contains(neighbour))
                        {
                            continue;
                        }

                        if (neighbour.HasKing)
                        {
                            ReversePathToKing(inProcessing, neighbour, buffer);
                            todo.Clear();
                            break;
                        }

                        if (neighbour.PointsTo(poppedSquare))
                        {
                            todo.Push(neighbour);
                            inProcessing.Add(neighbour);
                            continue;
                        }

                        if (FollowPathToKing(neighbour, formerKing, inProcessing, todo, buffer))
                        {
                            // Interessing part : the path to king is followed to see whether it is valid (ie doesn't cross inProcessing).
                            // If it is valid, this part is still connected to kings, and we repair the PathToKing.
                            // else the whole path is added to inProcessing for future correction
                            todo.Clear();
                            break;
                        }
                    }
                }

                foreach (Square lostSquare in inProcessing)
                {
                    LogProvider.StoreLog(new Log(
                                                  lostSquare.KingId,
                                                  baseSquare.KingId,
                                                  LogKind.ConnexityLoss,
                                                  lostSquare.Position));
                    lostSquare.KingId = King.NeutralKingId;
                    buffer.UpdateSquare(lostSquare);
                    connexityWasNotLost = false;
                }

                inProcessing.Clear();
            }

            buffer.AtomicCommit();
            return connexityWasNotLost;
        }

        /// <summary>
        /// WARNING : OLD VERSION KEPT ONLY IF THERE IS A BIG PROBLEM
        /// Verify if connexity is broken, and if it is, it repairs it any way it can, even partially.
        /// Needs not only the square, but also its former owner,
        /// Because, ownership have already changed due to an attack
        /// Called by AttackSolver.
        /// </summary>
        /// <param name="breakpoint">Wrapper upon the coordinates of the case to be examined and the Id of its former King</param>
        /// <returns>True iff it has succeeded to repair connexity fully</returns>
        public bool EnforceConnexityOld(ConnexityBreakpoint breakpoint)
        {
            var buffer = new ConnexityBuffer(GameProvider);
            var baseSquare = buffer.GetSquareByPosition(breakpoint.Position);
            var formerKing = GameProvider.GetKingById(breakpoint.FormerKingId);

            var inProcessing = new HashSet<Square>();
            var todo = new Stack<Square>();

            todo.Push(baseSquare);
            while (todo.Count != 0)
            {
                Square poppedSquare = todo.Pop();

                foreach (Square square in new NeighbourSquares(buffer, poppedSquare.Position))
                {
                    if (inProcessing.Contains(square) && square.PointsTo(poppedSquare))
                    {
                        QueueProvider.PutConnexityKingToCorrect(breakpoint.FormerKingId);
                        return false;
                    }

                    if (
                        !inProcessing.Contains(square) &&
                        square.PointsTo(poppedSquare) &&
                        square.KingId == formerKing.Id &&
                        !square.HasKing)
                    {
                        inProcessing.Add(square);
                        todo.Push(square);
                    }
                }
            }

            var previousCount = 0;

            // This loop is justified by the case where several connexity areas are cut from the king (see tests)
            // It rarely does more than one or two iterations
            while (previousCount != inProcessing.Count)
            {
                previousCount = inProcessing.Count;

                // We have here in inProcessing all the Pathes which formerly went through the "lost" square
                foreach (Square square in inProcessing)
                {
                    //// We seek among them all if one of them has a neighbour of the same owner which could be used as a new path
                    foreach (Square neighbour in buffer.GetNeighbours(square.Position))
                    {
                        if (!inProcessing.Contains(neighbour) && neighbour.KingId == formerKing.Id)
                        {
                            todo.Push(neighbour);
                            break;
                        }                        
                    }

                    if (todo.Count != 0)
                    {
                         break;
                    }
                }

                // We then link all we can to this new path
                while (todo.Count != 0)
                {
                    Square poppedSquare = todo.Pop();
                    foreach (Square squareToConnect in buffer.GetNeighbours(poppedSquare.Position))
                    {
                        if (inProcessing.Contains(squareToConnect))
                        {
                            squareToConnect.MakePointsTo(poppedSquare);
                            buffer.UpdateSquare(squareToConnect);
                            inProcessing.Remove(squareToConnect);
                            todo.Push(squareToConnect);
                        }
                    }
                }
            }

            foreach (Square square in inProcessing)
            {
                LogProvider.StoreLog(new Log(
                                              square.KingId,
                                              baseSquare.KingId,
                                              LogKind.ConnexityLoss,
                                              square.Position));
                square.KingId = King.NeutralKingId;
                buffer.UpdateSquare(square);
            }

            buffer.AtomicCommit();
            return inProcessing.Count == 0;
        }

        /// <summary>
        /// Called on a case just stolen or won in order to link this case to the new owner's king.
        /// Called directly by AttackSolver.
        /// If it cannot manage to create a PathToKing (an anomaly that can be caused by concurrent access), 
        /// it makes the case to go neutral.
        /// </summary>
        /// <param name="position">The position of the square to be updated.</param>
        /// <returns>True iff it is a success</returns>
        public bool ConnexityAnnexSquare(Point position)
        {
            var buffer = new ConnexityBuffer(GameProvider);
            var square = buffer.GetSquareByPosition(position);
            
            foreach (var neighbour in buffer.GetNeighbours(position))
            {
                if (neighbour.KingId == square.KingId)
                {
                    square.MakePointsTo(neighbour);
                    buffer.UpdateSquare(square);

                    var king = GameProvider.GetKingById(square.KingId);
                    king.SquaresRectangle = Rectangle.Union((new Rectangle(square.Position.X, square.Position.Y, 1, 1)), king.SquaresRectangle);
                    GameProvider.UpdateKing(king);

                    buffer.AtomicCommit();
                    return true;
                }
            }

            square.KingId = King.NeutralKingId;
            buffer.UpdateSquare(square);
            buffer.AtomicCommit();
            return false;
        }

        /// <summary>
        /// This batch function must NOT BE USED in normal time. 
        /// It could be used to globally check coherency of the map.
        /// </summary>
        public void ConnexityTotalChecker()
        {
            var everything = GameProvider.GetAllSquares();
            var sorted = everything.ToLookup(square => square.KingId);
            foreach (IGrouping<long, Square> grouping in sorted)
            {
                if (grouping.Key == King.NeutralKingId)
                {
                    continue;
                }

                RepairsConnexity(grouping.Key, grouping.ToDictionary(square => square.Position.ToAlphaString()));
            }
        }

        /// <summary>
        /// Repairs connexity in a set of squares for a given king
        /// Repairs SquaresRectangle and SquaresNumber
        /// </summary>
        /// <param name="kingId">The given king.</param>
        /// <param name="cases">The set of squares, indexed by position.toalphastring</param>
        public void RepairsConnexity(long kingId, Dictionary<string, Square> cases)
        {
            var king = GameProvider.GetKingById(kingId);
            if (king.IsNeutral())
            {
                return;
            }

            var notkingdom = new Dictionary<string, Square>(cases);
            notkingdom.Remove(king.Position.ToAlphaString());
            var kingdom = new List<Square>();
            var todo = new Queue<Square>();

            int maxx = int.MinValue, 
                minx = int.MaxValue, 
                miny = int.MaxValue, 
                maxy = int.MinValue;

            todo.Enqueue(cases[king.Position.ToAlphaString()]);
            while (todo.Count > 0)
            {
                var square = todo.Dequeue();
                kingdom.Add(square);
                minx = Math.Min(minx, square.Position.X);
                miny = Math.Min(miny, square.Position.Y);
                maxx = Math.Max(maxx, square.Position.X);
                maxy = Math.Max(maxy, square.Position.Y);
                foreach (Direction direction in new Directions())
                {
                    var pos = square.Position.GetDir(direction);
                    if (notkingdom.ContainsKey(pos.ToAlphaString())
                        && notkingdom[pos.ToAlphaString()].KingId == kingId)
                    {
                        var square2 = (Square) notkingdom[pos.ToAlphaString()].Clone();
                        square2.MakePointsTo(square);
                        notkingdom.Remove(pos.ToAlphaString());
                        todo.Enqueue(square2);
                    }
                }
            }

            //// here, _todo is empty, kingdom contains connexes, and notkingdom others which should not exist.

            foreach (var square in kingdom)
            {
                if (square.PathToKing != cases[square.Position.ToAlphaString()].PathToKing)
                {
                    GameProvider.UpdateSquare(
                        square.Position,
                        argSquare => UpdateSquare(argSquare, square));
                }
            }

            if (king.SquaresNumber != kingdom.Count)
            {
                king.UpdateAcademyTroops();
                king.SquaresNumber = kingdom.Count;
            }

            king.SquaresRectangle = new Rectangle(minx, miny, maxx - minx + 1, maxy - miny + 1);
            GameProvider.UpdateKing(king);
            foreach (var square in notkingdom.Values)
            {
                if (square.KingId == kingId)
                {
                    LogProvider.StoreLog(new Log(kingId, kingId, LogKind.ConnexityLoss, square.Position));
                    square.HasKing = false;
                    square.KingId = King.NeutralKingId;
                    GameProvider.UpdateSquare(square);
                }
            }
        }

        /// <summary>
        /// Corrects all the pathToKing of a set to make them pass through a given square.
        /// Clears the set at the end.
        /// If the set is not connex, or if the square is not adjacent to at least on case of that set, 
        /// the behaviour of this method is unspecified.
        /// </summary>
        /// <param name="inProcessing">The set of squares whose pathToKing must be updated</param>
        /// <param name="square">The target of the pathToKing</param>
        /// <param name="buffer">The buffer opened by the calling method. This calling method is then supposed to commit it at some point</param>
        private static void ReversePathToKing(HashSet<Square> inProcessing, Square square, IConnexityBuffer buffer)
        {
            var todo = new Stack<Square>();
            var processed = new HashSet<Square>();

            todo.Push(square);
            processed.Add(square);

            while (todo.Count != 0)
            {
                var poppedSquare = todo.Pop();
                foreach (var neighbour in buffer.GetNeighbours(poppedSquare))
                {
                    if (
                        inProcessing.Contains(neighbour) &&
                        !processed.Contains(neighbour))
                    {
                        neighbour.MakePointsTo(poppedSquare);
                        buffer.UpdateSquare(neighbour);
                        processed.Add(neighbour);
                        todo.Push(neighbour);
                    }
                }
            }

            inProcessing.Clear();
        }

        /// <summary>
        /// Updates a square based on its wanted new state(newSquare) 
        /// and the state it has acquired during process(oldSquare).
        /// Used by RepairsConnexity to do updates atomically.
        /// </summary>
        /// <param name="oldSquare">The square as given by GameProvider</param>
        /// <param name="newSquare">The square as wanted by RepairsConnexity</param>
        /// <returns>The square to be stored</returns>
        private static Square UpdateSquare(Square oldSquare, Square newSquare)
        {
            if (oldSquare.KingId != newSquare.KingId)
            {
                return oldSquare;
            }

            newSquare.Troops = oldSquare.Troops;
            return newSquare;
        }

        /// <summary>
        /// Used by EnforceConnexityOpt.
        /// It follows a pathToKing from a square, to a given king, while avoiding a set of squares.
        /// If it succeeds, it corrects the pathToKing of the squares of that set 
        /// (which is supposed to be adjacent to the origin square), and clear that set
        /// If it fails, it adds all the squares of the partial path, both to the set and to a stack passed in argument.
        /// </summary>
        /// <param name="square">The origin square of the path</param>
        /// <param name="king">The king to be joined by that path</param>
        /// <param name="inProcessing">The set of squares it cannot cross, and to which the partial path may be added</param>
        /// <param name="bigTodo">The stack to which to push the square sof the path in case of failure</param>
        /// <param name="buffer">The buffer opened by the calling method. This calling method is then supposed to commit it at some point</param>
        /// <returns>True iff it succeeds to go to the king</returns>
        private bool FollowPathToKing(Square square, King king, HashSet<Square> inProcessing, Stack<Square> bigTodo, IConnexityBuffer buffer)
        {
            var nextSquare = square;
            var oldSquare = square;
            var success = false;
            while (true)
            {
                if (nextSquare.KingId != king.Id)
                {
                    QueueProvider.PutConnexityKingToCorrect(king.Id);
                    break;
                }

                if (nextSquare.HasKing)
                {
                    ReversePathToKing(inProcessing, oldSquare, buffer);
                    success = true;
                    break;
                }

                if (
                    inProcessing.Contains(nextSquare))
                {
                    break;
                }

                inProcessing.Add(nextSquare);
                bigTodo.Push(nextSquare);
                oldSquare = nextSquare;
                nextSquare = buffer.GetSquareByPosition(nextSquare.Position.GetDir(nextSquare.PathToKing));
            }

            return success;
        }
    }
}